559C - Gerald and Giant Chess - CodeForces Solution

#include <iostream>
#include <algorithm>
#define int long long

using namespace std;

const int kM = 1e9 + 7;

int n, h, w, ans;
int dp[2010];
int fac[200010];

struct E {
    int x, y;
} e[2010];

bool cmp(E x, E y) {
    return x.x + x.y < y.x + y.y;
}

int Pow(int x, int y) {
    int sum(1);
    while (y) {
        if (y & 1) {
            sum = (sum * x) % kM;
        }
        x = (x * x) % kM;
        y >>= 1;
    }
    return sum;
}

int C(int x, int y) {
    return fac[x] * Pow(fac[y], kM - 2) % kM * Pow(fac[x - y], kM - 2) % kM;
}

signed main() {
    cin >> h >> w >> n;
    for (int i = fac[0] = 1; i < h + w; ++i) {
        fac[i] = fac[i - 1] * i % kM;
    }
    for (int i = 1; i <= n; ++i) {
        cin >> e[i].x >> e[i].y;
    }
    sort(e + 1, e + 1 + n, cmp);
    ans = C(h + w - 2, h - 1);
    for (int i = 1; i <= n; ++i) {
        dp[i] = C(e[i].x + e[i].y - 2, e[i].x - 1);
        for (int j = 1; j < i; ++j) {
            if (e[j].x <= e[i].x && e[j].y <= e[i].y) {
                dp[i] -= dp[j] *
                    C(e[i].x - e[j].x + e[i].y - e[j].y, e[i].x - e[j].x) % kM;
                dp[i] = (dp[i] % kM + kM) % kM;
            }
        }
        ans -= (dp[i] * C(h + w - e[i].x - e[i].y, h - e[i].x)) % kM;
        ans = (ans % kM + kM) % kM;
    }
    cout << ans;
    return 0;
}